package com.arron.algorithm.leetcodetop100.链表;

import com.arron.algorithm.leetcodetop100.ListNode;

/**
 * Leetcode 160. 相交链表 相交链表
 *
 */
public class 相交链表 {


    /**
     * 使用双指针的解法
     * 如果没有相交点最后都为null的时候同时跳出循环
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {

        if (headA ==null || headB ==null) return null;

        ListNode pA = headA;
        ListNode pB = headB;

        while (pA != pB){
            pA = pA ==null? headB : pA.next;
            pB = pB == null? headA : pB.next;
        }
        return pA;
    }


    /**
     * 先计算两个链表的长度差
     * 然后从对其长度开始遍历两个链表
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {

        if (headA ==null || headB ==null) return null;
        ListNode pA = headA;
        ListNode pB = headB;
        int lA = 0;
        int lB = 0;
        while (pA !=null){
            pA = pA.next;
            lA++;
        }

        while (pB !=null){
            pB = pB.next;
            lB++;
        }
        pA = headA;
        pB = headB;
        if (lA >lB){
            int d = lA-lB;
            for (int i = 0; i < d; i++) {
                pA = pA.next;
            }
        }

        if (lA < lB){
            int d = lB-lA;
            for (int i = 0; i < d; i++) {
                pB = pB.next;
            }

        }

        while (pA !=null && pB != null){
            if (pA == pB){
                return pA;
            }
            pA = pA.next;
            pB = pB.next;
        }

        return null;
    }

}
